import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-05-01
 * Time:11:23
 */

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class 两棵二叉搜索树中的所有元素 {
    class Solution {
        public void inorder(TreeNode root, List<Integer> list) {
            if(root != null) {
                inorder(root.left,list);
                list.add(root.val);
                inorder(root.right,list);
            }

        }
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> ret = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            inorder(root1,list1);
            inorder(root2,list2);
            int count1 = 0,count2 = 0;
            while(true) {
                if(list1.size() == count1) {
                    ret.addAll(list2.subList(count2,list2.size()));
                    break;
                }
                if(list2.size() == count2) {
                    ret.addAll(list1.subList(count1,list1.size()));
                    break;
                }
                if(list1.get(count1) < list2.get(count2)){
                    ret.add(list1.get(count1++));
                }else {
                    ret.add(list2.get(count2++));
                }
            }
            return ret;
        }
    }
}
